﻿using System;
using System.Collections.Generic;
using System.Data.Entity;
using System.Linq;
using System.Web;
using SearchWebApplication.Models;

namespace SearchWebApplication.Classes
{
    public class ContactSearcher
    {
        private ContactContext db;

        public ContactSearcher(ContactContext context)
        {
            db = context;
        }

        public List<Contact> search(string query)
        {
            List<Contact> list = db.Contacts.ToList<Contact>();
            List<LevenshteinStruct> sortList = new List<LevenshteinStruct>();
            List<Contact> results;

            sortList = rankName(list, query);

            results = new List<Contact>(sortList.Count());

            for (int i = 0; i < sortList.Count(); i++)
            {
                results.Add(sortList.ElementAt(i).tokenOwner);
            }

            return results;
        }

        private List<LevenshteinStruct> rankName(List<Contact> contacts, string query)
        {
            List<LevenshteinStruct> list = new List<LevenshteinStruct>(contacts.Count());
            foreach (Contact c in contacts)
            {
                list.Add(new LevenshteinStruct(c, tokenizedEditDist(query, c.name), c.name));
            }

            list.Sort();

            return list;
        }

        //returns the sum of the levenshtein distances of each string token delimited by a space
        // OR the levinshtein distance of the a whole string comparison
        
        //The terms are named search and comparison because this algorithm is more forgiving to the 
        // first string
        private int tokenizedEditDist(string search, string comparison)
        {
            string[] tokens1 = search.Split(' ');
            string[] tokens2 = comparison.Split(' ');
            int[,] editDistances = new int[tokens1.Length, tokens2.Length];
            int[] shortDistances = new int[tokens1.Length];
            int sum = 0;

            int i;
            int j;
            //Fills array with edit distances for string tokens
            for (i = 0; i < editDistances.GetUpperBound(0); i++)
            {
                for (j = 0; j < editDistances.GetUpperBound(0); j++)
                {
                    editDistances[i, j] = LevenshteinStruct.levenshteinDist(tokens1[i], tokens2[j]);
                }
            }
            //Takes shortist edit distance from each row and inserts it into postion i in shortDistances
            for (i = 0; i < editDistances.GetUpperBound(0); i++)
            {
                int temp = editDistances[i, 0];
                for (j = 0; j < editDistances.GetUpperBound(0); j++)
                {
                    if (temp > editDistances[i, j])
                    {
                        temp = editDistances[i, j];
                    }
                }
                shortDistances[i] = temp;
            }
            //sum of edit distances
            for (i = 0; i < shortDistances.Length; i++)
            {
                sum += shortDistances[i];
            }

            return Math.Min(sum, LevenshteinStruct.levenshteinDist(search, comparison));
        }

    }

    public class LevenshteinStruct : IComparable
    {
        public int editDist { get; set; }
        public string token { get; set; }
        public Contact tokenOwner  { get; set; }

        //returns the smallest edit distance of two strings
        public static int levenshteinDist(string st1, string st2)
        {
            int[,] array = new int[st1.Length, st2.Length];
            int i = 0;
            for (i = 0; i < st1.Length; i++)
            {
                array[i, 0] = i;
            }

            int j = 0;
            for (j = 0; j < st2.Length; j++)
            {
                array[0, j] = j;
            }

            for (i = 1; i <= array.GetUpperBound(0); i++)
            {
                for (j = 1; j <= array.GetUpperBound(1); j++)
                {
                    if (st1[i - 1] == st2[j - 1])
                    {
                        array[i, j] = array[i - 1, j - 1];
                    }
                    else
                    {
                        array[i, j] = Math.Min(
                            Math.Min(array[i - 1, j] + 1, array[i, j - 1] + 1),
                        array[i - 1, j - 1] + 1);
                    }
                }
            }

            return array[i - 1, j - 1];
        }


        public LevenshteinStruct(Contact contact, int dist, string s)
        {
            editDist = dist;
            tokenOwner = contact;
            token = s;
        }

        //Implements IComparable so it can be sorted by a generic collection
        public int CompareTo(object obj)
        {

            if (obj.GetType() == this.GetType())
            {
                return this.editDist - ((LevenshteinStruct)obj).editDist;
            }
            else
            {
                return 1;
            }
        }
    }
}